/* 找到p和q最近公共祖先结点r */

#include <iostream>
#include "BiTreefun.h"
using namespace std;
#define maxsize 50

// 找到最近公共祖先结点 -- 后序遍历，找到p、q
BiTree Nonpost(BTNode *bt, BTNode *p, BTNode *q)
{
  // 创建3个栈
  BTNode *St[maxsize], *tag = NULL;
  BTNode *s1[maxsize], *s2[maxsize];
  int top = -1, top1 = -1, top2 = -1;
  
  // 访问的结点不为空 或者 0号栈不为空
  while (bt || top != -1)
  {
    // 访问结点不为空
    if (bt != NULL)
    {
      // 进0号栈
      St[++top] = bt;
      
      // 到左孩子结点
      bt = bt->lchild;
    }
    
    // 访问结点为空
    else
    {
      // 取出0号栈的栈顶元素
      bt = St[top];
      
      // 如果有右孩子 并且 右孩子没有被访问
      if (bt->rchild && bt->rchild != tag)
        bt = bt->rchild; // 到右孩子结点
      
      // 否则
      else
      {
        // 0号栈元素出栈
        bt = St[top--];
        
        // 如果是p结点 -- 用1号栈记录p结点的所有双亲结点
        if (bt == p)
        {
          int temp = top;
          while (temp != -1)
            s1[++top1] = St[temp--];
        }
        
        // 如果是q结点 -- 用2号栈记录q结点的所有双亲结点
        if (bt == q)
        {
          int temp = top;
          while (temp != -1)
            s2[++top2] = St[temp--];
        }
        
        // 记录上一次访问的元素
        tag = bt;
        bt = NULL;
      }
    }
  }
  
  // 找到最近共同双亲结点并返回
  for (int i = 0; i<=top1; ++i)
    for (int j = 0; j<=top2; ++j)
      if (s1[i] == s2[j])
        return s1[i];
      
  // 没有共同双亲结点
  return NULL;
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  
  // p指向一个结点
  BTNode *p = T->lchild->lchild;
  
  // q指向一个结点
  BTNode *q = T->lchild->rchild->rchild;
  
  // 找到最近公共祖先结点
  cout << Nonpost(T, p, q)->data;
  return 0;
}
